package org.TheSubject;


import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 *     左括号必须用相同类型的右括号闭合。
 *     左括号必须以正确的顺序闭合。
 *
 */
public class Solution20OfHot {
    static Map<Character, Character> pairs = new HashMap<Character, Character>() {{
        put(')', '(');
        put(']', '[');
        put('}', '{');
    }};

    public boolean isValid(String s) {
        int length = s.length();
        if (length==0){
            return false;
        }
        if ((length&1)!=0){
            return false;
        }
        Deque<Character> deque=new LinkedList<>();
        for (int i=0;i<length;i++){
            Character c=s.charAt(i);
            Character peek = deque.peek();
            Character character = pairs.get(c);
            if (peek!=null&&peek.equals(character)){
                deque.poll();
            }else {
                deque.push(c);
            }
        }
        return deque.isEmpty();
    }

    public static void main(String[] args) {
        Solution20OfHot solution20OfHot = new Solution20OfHot();
        System.out.println(solution20OfHot.isValid("([)]"));
    }
}
